#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct Node{
	ElemType data;
	struct Node *next;	
}Node;
typedef Node *LinkList;

bool GetElem(LinkList L, int i, ElemType *e){
	int j = 1;
	LinkList p;
	p = L->next;
	while(p && j < i){
		p = p->next;
		j++;
	}
	if(!p || j>i){
		return false;
	}
	*e = p->data;
	return true;
}

bool ListInsert2(LinkList L, int i, ElemType e){
	int j = 1;
	LinkList p, n, last;
	p = L->next;
	while(p && j < i){
		last = p;
		p = p->next;
		j++;
	}
	n = (Node *)malloc(sizeof(Node));
	n->data = e;
	if(!p || j>i){
		return false;
	}
	n->next = last->next;
	last->next = n;
	return true;
}

bool ListInsert3(LinkList L, int i, ElemType e){
	int j = 1;
	LinkList p, n;
	p = L;
	while(p && j < i){
		p = p->next;
		j++;
	}
	n = (Node *)malloc(sizeof(Node));
	n->data = e;
	if(!p || j>i){
		return false;
	}
	n->next = p->next;
	p->next = n;
	return true;
}

bool ListDelete2(LinkList L, int i, ElemType *e){
	int j = 1;
	LinkList p, last;
	p = L->next;
	while(p && j < i){
		last = p;
		p = p->next;
		j++;
	}
	if(!p || j > i){
		return false;
	}
	*e = p->data;
	last->next = p->next;
	free(p);
	return true;
}

bool ListDelete3(LinkList L, int i, ElemType *e){
	int j = 1;
	LinkList p, tmp;
	p = L;
	while(p && j < i){
		p = p->next;
		j++;
	}
	if(!p || j > i){
		return false;
	}
	*e = p->data;
	tmp = p->next;
	p->next = tmp->next;
	free(tmp);
	return true;
}



//入参为指向指针的指针
bool ListInsert(LinkList *L, int i, ElemType e){
	int j = 1;
	LinkList p, n;
	p = *L;
	while(p && j < i){
		p = p->next;
		j++;
	}
	n = (Node *)malloc(sizeof(Node));
	n->data = e;
	if(!p || j>i){
		return false;
	}
	n->next = p->next;
	p->next = n;
	return true;
}

//入参为指向指针的指针
bool ListDelete(LinkList *L, int i, ElemType *e){
	int j = 1;
	LinkList p, q;
	p = *L;
	while(p && j < i){
		p = p->next;
		j++;
	}
	if(!p || j > i){
		return false;
	}
	*e = p->data;
	q = p->next;
	p->next = q->next;
	free(q);
	return true;
}

bool CreateListHead(LinkList *L, int i){
	LinkList p;
	*L = (Node *)malloc(sizeof(Node));
	(*L)->next = NULL;
	for(int j = 0;j < i; j++){
		p = (Node *)malloc(sizeof(Node));
		p->data = j; 
		p->next = (*L)->next;
		(*L)->next = p;
	}
	return true;
}

bool CreateListTail(LinkList *L, int i){
	LinkList p, r;
	*L = (Node *)malloc(sizeof(Node));
	r = *L;
	for(int j = 0;j < i; j++){
		p = (Node *)malloc(sizeof(Node));
		p->data = j;
		r->next = p; 
		r = p;
	}
	r->next = NULL;
	return true;
}

void PrintList(LinkList *L){
	printf("%p\n", *L);
	LinkList p;
	p = (*L)->next;
	while(p){
		printf("%d ", p->data);
		p=p->next;
	}
	printf("\n");
}

void PrintList2(LinkList L){
	printf("%p\n", L);
	LinkList p;
	p = L->next;
	while(p){
		printf("%d ", p->data);
		p=p->next;
	}
	printf("\n");
}

int main(){
	LinkList l1, l2, l3;
	ElemType e;

	CreateListHead(&l1, 5);
	PrintList2(l1);
	PrintList2(l1);

	printf("---\n");

	CreateListTail(&l2, 5);
	PrintList(&l2);
	ListInsert(&l2, 3, 9);
	PrintList(&l2);
	ListDelete(&l2, 4, &e);
	PrintList(&l2);


	printf("---\n");
	CreateListTail(&l3, 5);
	PrintList(&l3);
	ListInsert2(l3, 3, 9);
	ListInsert2(l3, 3, 9);
	PrintList(&l3);
	ListDelete2(l3, 4, &e);
	PrintList(&l3);
	ListDelete3(l3, 4, &e);
	PrintList(&l3);
	return 0;
}
